package com.andnnl.stack;

import java.util.Stack;

/**
 * Created by chenss on 2021/9/9.
 */
public class MazeTest {


    public static void main(String[] args) {
        int[][] map = {
                {1, 1, 0, 0, 1, 1, 1, 1, 1},
                {1, 1, 0, 0, 1, 0, 0, 1, 1},
                {0, 1, 1, 1, 1, 0, 1, 1, 1},
                {1, 0, 1, 0, 1, 0, 1, 0, 0},
                {1, 1, 0, 1, 0, 1, 1, 0, 1},
                {1, 1, 0, 1, 0, 1, 0, 1, 1},
                {1, 1, 0, 1, 0, 1, 1, 1, 1},
                {1, 1, 0, 1, 0, 1, 1, 0, 1},
        };
        print(map);
        int row = map.length;
        int col = map[0].length;

        Stack<F> stack = new Stack<>();
        int r = 0;
        int c = 0;
        int lastR = 0;
        int lastC = 0;
        int fx = 0;//0123：右下左上
        int count = 0;
        while (true) {
            count++;
            int k = map[r][c];
//            System.out.println("r:"+r+",c:"+c+",k:"+k+",fx:"+fx);
            if (k == 1) {
                map[r][c] = 2;//走过的路改为2
                stack.push(new F(r, c, fx, lastR, lastC));
                lastR = r;
                lastC = c;
//                print(map);
                if (r == row - 1 && c == col - 1) {
//                    System.out.println("结束");
                    print(map);
                    break;
                }
                fx = -1;

            } else if (fx > 3) {
                //走过的路,或者没路
                //走过所有的方向,回退
//                    System.out.println("回退");
                F f = stack.pop();
                r = f.r;
                c = f.c;
                map[r][c] = 1;//走过的路恢复改为1
                lastR = f.lastR;
                lastC = f.lastC;
                fx = f.fx;
//                    continue;

            }
            fx++;
            //0123：右下左上
            if (fx == 0) {
                c = lastC + 1;
                r = lastR;
                if (c >= col) {
                    c = col - 1;
                }
            } else if (fx == 1) {
                r = lastR + 1;
                c = lastC;
                if (r >= row) {
                    r = row - 1;
                }
            } else if (fx == 2) {
                c = lastC - 1;
                r = lastR;
                if (c < 0) {
                    c = 0;
                }
            } else if (fx == 3) {
                r = lastR - 1;
                c = lastC;
                if (r < 0) {
                    r = 0;
                }
            }
        }
        System.out.println(count);
    }

    static class F {
        int r = 0;//行
        int c = 0;//列
        int fx = 0;//方向
        int lastR = 0;//上一个的行
        int lastC = 0;//上一个的列

        public F(int r, int c, int fx, int lastR, int lastC) {
            this.r = r;
            this.c = c;
            this.fx = fx;
            this.lastR = lastR;
            this.lastC = lastC;
        }
    }

    static void print(int[][] a) {
        for (int i = 0; i < a.length; i++) {
            int[] b = a[i];
            for (int j = 0; j < b.length; j++) {
                System.out.print(b[j] + "  ");
//                if (j == b.length) System.out.println("");
            }
            System.out.println();
        }
        System.out.println("--------------------------");
    }
}
